//https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
package codeRandomThoughts.Test1047删除字符串中的所有相邻重复项;

import java.util.Arrays;
import java.util.Stack;

/**
 * 两种方法
 * 用栈
 * 用双指针
 */
public class Solution2 {

    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (!stack.isEmpty() && stack.peek() == s.charAt(i)) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }

        //反转字符串
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        sb.reverse();
        return sb.toString();
    }

    /**
     * 双指针法
     * 超级快
     *
     * @param s
     * @return
     */
    public String removeDuplicates2(String s) {
        char[] charArray = s.toCharArray();
        int slow = 0;
        int fast = 0;
        for (fast = 1; fast < charArray.length; fast++) {
            if (slow < 0 || charArray[fast] != charArray[slow]) {
                slow++;
                charArray[slow] = charArray[fast];
            } else {
                slow--;
            }
        }

        char[] chars = Arrays.copyOfRange(charArray, 0, slow + 1);
        return new String(chars);
    }
}
